本章将首先分析RSPSI方法系列的模型构建思路，并在模型可解释性和工程性方向上，指出该系列方法面对大规模社交网络数据的不足之处。
进一步地，本章将介绍分析典型的用于扩展大规模图机器学习问题的方法，结合这一系列思路提出为大规模社交网络场景设计的改进版本的多源点检测方法CRSPSI，并从整体实现思路和工程优化细节等若干方面详细介绍这一模型的设计和实现。


\section{大规模社交网络源点检测任务研究现状与研究动机分析}\label{subsec:rspsi-whole-analysis}

\subsection{现有方法复杂度分析}
类似于绝大多数现有的多源点检测方法\cite{fan_temp_gcnsi_2020,ling_sl_vae_2022,wang_ivgd_2022,hou_tgasisequential_2023}，RSPSI方法也是通过在完整的社交网络图结构上构建一系列机器学习模块来进行标签传播特征和节点拓扑结构的学习，进而对传播源做出预测。这样的做法不具有向更大规模社交网络图数据进行扩展的能力，具体原因主要在于以下两点：

\begin{itemize}
    \item 对于社交网络图结构$G=(V,E)$，根据网络稠密程度，其边的数量$|E|$随网络节点数增大而呈现次线性或超线性增加。典型的图神经网络模块需要处理邻居节点之间的特征聚合，因此对应用在对应图数据中，输入维度为$d$的每一层图神经网络层，其计算的空间复杂度是$O(|V|^2d)$，经稀疏矩阵乘法优化后可以达到$O(|E|d)$或$O(|V|kd)$；而对于本文（输入输出维度相同）的情景，图神经网络的存储和计算空间复杂度则会增长的更快，需要存储额外权重矩阵的GAT和GATv2模型的计算复杂度达到了$O(|V|d+|E|+|V|^2+d^2)$。可以预见，随着社交网络图结构规模的增长，图神经网络模块在扩展其规模时，会面临空间和时间复杂度增加与表征能力下降的两难困境；
    \item 由\autoref{fig:rspsi-s-transformer}可以看出，使用类似Graph-Bert的序列转换方式会将标签快照序列张成一维token序列，这意味着token长度达到了$M|V|$，对应地在单层Transformer模块中计算的时间复杂度和空间复杂度分别达到了$O(M|V|d_{model}^2+m^2|V|^2d_{model})$和$O(M|V|d_{model}+hM^2|V|^2+d_{model}^2)$，随序列长度和节点数量平方级增长的时间和空间复杂度对于RSPSI模型的训练和预测来说压力都是极大的。然而随着节点数量的增加，与图数据中特定节点具有强注意力作用的节点数量并不会显著增加，因此在Transformer层的计算过程中，必然会存在大量的不必要的自注意力计算。
\end{itemize}
\subsection{大规模图机器学习任务可扩展性研究动机分析}
工业界和学术界针对随现实世界社交网络不断扩大而引起的图机器学习的规模扩大开展了一系列算法和工程方向的研究与实践，期望能够解决大规模图机器学习的可扩展性问题。本节将简要阐述这一系列工作中为本文研究提供重要动机的一系列研究工作，并以这些核心思路出发，引出本章提出的CRSPSI方法的核心设计。

\subsubsection{基于Offloading策略的推理方法}\label{subsec:cur_offloading_method}
机器学习领域中的 Offloading \cite{mach2017mobileoffloading}方法指的是将部分计算密集型任务从核心计算设备（以GPU类设备为主）移动到边缘计算设备（如CPU、云端计算平台和边缘计算平台），以减少本地计算负担、提高总和计算效率，并充分计算资源来加速机器学习任务的执行的系列方法。在本文的研究中，可以使用Offloading方法分步分块计算不足以完全在GPU中执行训练和预测任务的模型，使得计算任务在CPU和GPU中并行执行，从而提升模型在时间和空间上的可扩展性。
\begin{figure}[htbp]
    \centering
    \includegraphics[width=\textwidth]{lzy/offloading-method.png}
    \caption{\label{fig:offloading-method}两种典型Offloading方法示意图}
\end{figure}

如\autoref{fig:offloading-method}所示，Song等人\cite{song2023powerinfer}总结出了两种典型的Offloading模式。其中，左侧以FlexGen\cite{sheng2023flexgen}框架为代表的以GPU为中心的Offloading方法周期性地将深度学习模块从CPU主存移入GPU内存中计算，待一个深度学习层执行完成后将对应模块移出，并随即移入后续深度学习层，整个模型运算期间，CPU不参与主要运算；而右侧以llama.cpp\cite{gerganov2023llama}为代表的GPU-CPU混合Offloading方法则尽可能地将整个模型的最后若干层深度学习模块放入GPU，然后在CPU上计算前半部分推理任务，将中间结果送入GPU中执行剩余计算，在运算期间CPU和GPU都参与处理。

Offloading方法能够在显存不足的情况下充分利用GPU算力，提升模型整体运行速度，但上述的方法依然有一系列的局限。一方面，上述方法都仅针对大语言模型的推理场景，对于需要在GPU上进行梯度反向传播和参数更新的训练场景支持能力有限；另一方面，上述两种Offloading方法都不可避免地要使得CPU或GPU一方处于等待状态，这也导致了一定程度的算力浪费。
本文的工作旨在提出一种既能支持模型训练流程，又能充分利用CPU和GPU两端算力的训练调度方法。

\subsubsection{基于图分割算法的扩展方法}

当基于子图划分的图神经网络分块处理模式是提升可图机器学习任务可扩展性的有效方法之一，Chiang等人\cite{chiang_cluster-gcn_2019}提出的Cluster-GCN模型在这一方向做出了建设性工作。
\begin{figure}[htbp]
    \centering
    \includegraphics[width=.5\textwidth]{lzy/metis.png}
    \caption{\label{fig:metis}METIS图分割算法与随机图分割方法效果对比示意图}
\end{figure}

Cluster-GCN使用METIS\cite{karypis1997metis}图分割算法将社交网络完整图数据划分为若干子图。如\autoref{fig:metis}所示，METIS算法的整体思想是，在将完整图数据划分为若干个子图后，使得跨子图节点间的边的数量最小化，这一做法很好地契合了社交网络图数据中体现的社群传播特性和小回路传播特性，使得每个切分得到的子图在信息传播中成为一个相对更独立的传播区域。在具体方法实现上，METIS首先通过节点合并等手段将图数据量缩小化得到粗图（Coarse Graph），之后基于粗图进行基于贪心算法的划分处理，再进一步对每个初步得到的子图进行细化（Uncoarsing）与节点调整，并得到最终的图划分结果。

本文也将图分割技术和以子图为单位的机器学习训练流程作为核心设计驱动点，为每个子图独立维护深度神经网络模块，并通过以子图模型为整体模型的最小训练单位来构建大规模图数据集下的源点检测任务框架。

\section{方法与创新点概述}

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\textwidth]{lzy/crspsi-s.pdf}
    \caption{\label{fig:crspsi-s}基于子图处理和权重判别模型的CRSPSI方法示意图}
\end{figure}
基于以上研究动机，本章提出基于子图处理和权重判别模型的面向大规模图数据的源点检测算法CRSPSI（Cluster-RSPSI）及其在两种深度学习训练模式下的实现，其整体架构如\autoref{fig:crspsi-s}所示。本章所提出方法的整体实现思路及其创新点可简单归为如下若干点：

\begin{itemize}
    \item 本章通过使用图分割算法，以最小化分割后子图间连接数为目标，将整图数据划分为一系列子图，并在每个子图上按照机器学习训练模式分别构建相应的RSPSI-S或RSPSI-E模型。本文创新性地提出了以子图处理模式统一模型的训练和预测两种流程，大幅降低了最细粒度下的模型计算复杂度，降低了大规模图数据场景下的硬件能力要求；
    \item 本章创新性地构建了子图模型共用的子图权重判别器以表征社交网络图数据中的社群传播特征，其通过接受标签快照序列整体和节点拓扑数据两个维度的特征。这一判别器既可以调和子图独立训练产生的数值差异，也可以更好地表征子图划分产生的社群特征；
    \item 本章提出的模型在工程实现上采用了基于Offloading的训练和预测流程，通过以子图模型及其计算流程为控制单元，创新性地构建了以GPU为主、同时充分利用CPU剩余算力的GPU-CPU协作训练和预测方法，确保整个模型的训练和预测流程即使在显存有限的情况下也能顺利、高效地进行。
\end{itemize}


\section{基于子图处理和权重判别模型的源点检测算法CRSPSI}
\subsection{整体架构设计}
\subsubsection{图分割算法与独立子图模型构建}

CRSPSI使用METIS图划分算法，基于子图划分的结果构建其核心流程。如\autoref{fig:crspsi-s}所示，其将前述章节中在社交网络完整图结构上构建的机器学习模块，分散且独立地构建在了每个分割后的子图上。在输入层面上，从完整图数据中抽取的标签快照、快照序列和节点拓扑特征仍然保持不变，但在将原始的特征数据输入模型中时，每一个子图对应的RSPSI模型只会截取其所在子图内的节点对应的三个维度的输入数据，并仅基于这些节点及其切分后的子图拓扑构建图神经网络、MLP-Mixer和相关Transformer层模块。相应地，子图对应的RSPSI模型也仅仅会输出所在子图内的节点置信评分或预测快照，这些部分输出值会在所有子图模块计算完成后被拼接并最终生成完整的输出结果。

上述基于子图划分与子图独立模型的训练和预测方法的设计思路是，标签传播这一行为本身就具有很强的社群特征，因此将对于节点特征聚合嵌入、特征融合和自注意力计算的视野从整个图数据聚焦在其所在的子图代表的社群中时，就能大幅提高节点社群特征的表征能力。此外，基于\autoref{subsec:rspsi-whole-analysis}的分析，Transformer层中自注意力计算部分的时间复杂度和空间复杂度都正比于节点数量的平方，因此通过将整图划分为$C$个子图，可以减少这部分的理论计算时间和占用空间到原值的$1/C$。



在训练过程的实现上，CRSPSI为每一个子图上构建的RSPSI模块设置了如\autoref{fig:crspsi-s}所示的训练、预测输出流和参数学习机制。
对使用先验源点数据进行监督学习方法训练的CRSPSI-S，每一个子图对应的RSPSI的输出评分将直接拟合其子图对应节点是否是源点的真实情况；
而对于拟合现有序列进行自监督学习方法训练的CRSPSI-E，每个子图对应的RSPSI输出的部分预测标签快照也会直接拟合这一标签快照序列在该子图中的节点对应的原始标签值。
不论采用何种训练方法，整个计算图构建、前向传播、损失计算、反向传播和梯度更新的流程都可以对单个子图内的模型独立进行，而不需要将所有子图的模型数据都移动到主设备进行更新。这样的特性使得本文构建的基于图分块的神经网络模型得以以子图为粒度独立执行基于已有数据的参数训练过程，而不仅仅局限于不需要更新参数的预测过程。

\subsubsection{基于子图权重判别器的动态权重模型}
仅在子图上构建同构的机器学习模型这一行为并不足以充分发挥和利用将全量图数据切分为子图所体现的图社区特征显著性和传播行为本地性。
一方面，传播实体在完整社交网络图中进行传播这一过程在同子图中的体现形式可能有较大差异：
有些子图中在传播开始时内部具有传播源点，因此在传播初期就呈现出感染者比例较高且呈网状散步的特征；
有些子图本身节点不是传播源，但可能在传播过程中接受其他子图节点的标签传播而感染，这些子图会在晚期才会呈现出传播模式的特征；
而大规模社交网络结构中，甚至会有相当数量的子图在标签传播过程中完全没有接收到该标签，这些子图应当被认为含有源点的概率极低。
另一方面，从数值稳定性和统一性层面分析，使用基于分割后的子图进行分块训练的方法会使得模型的准确性和鲁棒性受到影响。RSPSI模型会对最终评分置信向量做一次统一的LayerNorm操作，这会使得对所有节点的预测数值的数值分布保持一致。但对于CRSPSI，由于需要在子图层面进行训练，LayerNorm的维度只在子图层面进行，这会使得不同子图的输出评分对一个一致的“传播源显著性”的评判标准无法保证比较关系的一致性，这可能会导致传播行为出现较晚、较少的子图中的节点的传播源显著性评分被高估，因此需要提供一定手段对不同子图输出的数值进行调和。

基于上述分析，本章提出的CRSPSI方法增加了如\autoref{fig:crspsi-s}所示的子图权重判别器（Subgraph Weighter）模块，用于体现子图传播模式的差异性，同时通过加权方式平衡不同子图的训练和预测输出的数值分布。

子图权重判别器的主要构成是一个MLP-Mixer模块，它仅仅接受标签快照序列维度和节点拓扑维度的特征数据，这意味着对于指定的标签传播快照序列和一个给定的子图$G_c=\{V_c,E_c\}$，子图权重判别器的接收输入是$X^{SW-raw}_c\in \mathbb{R}^{N_c\times(K^{seq}+K^{top})}$。这一输入首先会通过一次平均池化压缩节点数量这一维度，随后再与其他子图进行拼接，因为子图权重判别器希望掌握的数据是某个给定子图上的整体标签传播情况数据，而不是某个特定的节点，经过处理后，子图权重判别器将持有被切分成的$C$个子图传入的共计为$X^{SW}\in \mathbb{R}^{C\times(K^{seq}+K^{top}) }$的中间数据向量。基于这一中间数据，其构建了一个以每一个子图为Patch概念，以所输入的$K^{seq}+K^{top}$维度的特征为Channel概念的两维度混合MLP-Mixer，其构建方法与前述\autoref{fig:mixer}所示典型MLP-Mixer大体相同，此处不再赘述。
这一MLP-Mixer的最后一个全连接线性层将被设置为输入数据维度为$K^{seq}+K^{top}$，输出维度为1，它将产生整个子图权重判别器对每个子图的权重评分$w\in \mathbb{R}^{C}$。

基于上述评分，CRSPSI可以基于其子图下构建的RSPSI方法经平衡后输出最终结果。对于监督学习模式构建的RSPSI-S方法评分$O^{final}$，得到如下公式所示的整图节点的源点置信评分：
\begin{equation}
    \label{equ:crspsi-s-output}
    \hat{O}^{final} = Concat(\{ O^{final}_i\mid i \in [1,C] \})w
\end{equation}

对于自监督学习模式的CRSPSI-E方法，同样可以得到经过上述评分加权得到的节点标签快照预测值，在此不再赘述。





\subsection{基于Offloading的可扩展训练与预测方法}\label{subsec:offloading-process}


由前述\autoref{subsec:cur_offloading_method}分析，现有的Offloading方法均会一定程度上限制计算资源，并且其使用场合大多仅局限于不需要反向传播和参数更新的预测场景，本章针对这两个局限性，提出了如\autoref{fig:crspsi-offloading-train}和\autoref{fig:crspsi-offloading-predict}所示的基于GPU-CPU协作处理的CRSPSI模型训练与预测方法。
\begin{figure}[htbp]
    \centering
    \includegraphics[width=\textwidth]{lzy/crspsi-offloading-train.pdf}
    \caption{\label{fig:crspsi-offloading-train}基于GPU-CPU协作处理的CRSPSI训练方法}
\end{figure}

在训练过程中，以子图模型计算任务为单位，将整个轮次的计算和仅在训练过程存在的反向传播、参数更新流程打包成共$C$个任务体，放入如\autoref{fig:crspsi-offloading-train}所示的双端队列中。
在整个训练过程中，由于子图权重判别器的计算结果和参数训练过程需要与所有的子图计算任务共同进行，因此子图权重判别器的参数和计算流程将始终被放置在GPU中。子图的大小和输入相关的数据维度确定时，就可以大体计算出训练过程中存储数据、模型、中间值和最终结果的显存总消耗量\cite{zhang2019efficient}，基于这一预估数值，可以让GPU一次处理其可以处理的最大数量的子图计算任务$B^{GPU}$。在完成$B^{GPU}$个子图下的模型计算、梯度反向传播和参数更新后，这一部分的RSPSI模型又会被移到主存上，从而为下一批子图计算任务腾出空间。

上述以子图任务而非机器学习模型的Layer为切分粒度的Offloading方法，可以使得整条子图计算链路得以在一个训练轮次内完成数据计算和参数更新流程，提供了有限显存条件下的训练能力可扩展性。基于这一关键特性，CRSPSI得以在极度有限的显存资源下在规模极大的社交网络图数据中构建。

进一步地，一个重要的观察是，在典型机器学习训练和预测任务负载下，当CPU仅作为GPU任务的调度器使用时，其负载往往并不能被充分利用\cite{kaleem2014adaptive,tang2020cpu}。
因此为了利用GPU训练过程中未完全被使用的CPU算力，本章提出了不同于已有的Offloading方法的GPU-CPU并行的训练策略。

如\autoref{fig:crspsi-offloading-train}所示，在调度GPU工作的同时，CPU本身还会从双端队列的另一端获取子图计算任务执行，并在本地维护一个子图权重判别器模型的拷贝，如此一来就有了仅在CPU侧产出子图计算任务的最终结果的能力。
当CPU侧子图计算任务完成后，反向传播不仅会计算CPU上计算的子图对应的RSPSI模块的模型参数的梯度，还会计算CPU上的子图权重判别器的模型参数的梯度。
但此处CRSPSI方法仅会为子图下的RSPSI机器学习模块内的参数配备优化器并用优化器来更新参数，在CPU上的子图权重判别器仅会通过反向传播积累梯度，并不持有优化器，也不会调用优化器使用梯度更新模型参数。
在所有CPU侧的子图任务执行完成后，其上的判别器积累了所有来自CPU上子图计算任务积累的梯度，此时只需要将这些梯度数据迁移到GPU上，并直接累加到GPU侧固定的判别器模型参数的梯度中，就得到了调整所有子图计算任务结果后的子图权重判别器参数的全量梯度，这时再使用仅为处于GPU上的子图权重判别器更新参数的优化器更新其参数，就能够完成一整个轮次的训练任务。
在子图权重判别器完成一个批次的参数更新后，应当将其模型再次拷贝一份到CPU上，以确保CPU中始终保存最新版本的子图权重判别器。
\begin{figure}[htbp]
    \centering
    \includegraphics[width=\textwidth]{lzy/crspsi-offloading-predict.pdf}
    \caption{\label{fig:crspsi-offloading-predict}基于GPU-CPU协作处理的CRSPSI预测方法}
\end{figure}

对于模型预测步骤，由于不需要考虑梯度反向传播和参数更新，其处理流程是训练任务的全面简化版本。如\autoref{fig:crspsi-offloading-predict}所示，在CRSPSI模型的源点预测流程中，GPU部分的处理方式与前述训练流程类似，但CPU部分将不再保留子图权重判别器的拷贝和计算结果，而是直接将中间结果产出到GPU中，使用GPU中常驻的判别器作为数值加权的依据。

\subsection{损失函数}

对于CRSPSI-S和CRSPSI-E子图模型，其损失函数计算与前述第\ref{chap:rspsi}章所述的RSPSI-S和RSPSI-E模型的损失函数完全相同，此处不再赘述。CRSPSI模型架构中的子图权重判别器从每个子图任务的损失函数计算中获取梯度，并仅仅基于这一梯度数值更新参数，因此不需要额外的损失函数。


\subsection{杂项设计和实现讨论}

\subsubsection{CRSPSI方法的参数更新策略}
\autoref{fig:crspsi-s}展示了在模型训练过程中，子图权重判别器不同于每个子图上各自独立构建的深度学习模块的参数更新过程。在子图上独立构建的RSPSI模块基于加权之后的源点置信评分或对应的部分节点标签预测快照作为最终输出计算损失函数，进行反向传播，并由各自独立的优化器进行参数更新，这一参数更新的粒度是一次子图处理轮次。

与此同时，可以注意到在每个子图处理轮次进行梯度反向传播过程时，梯度数值也会传播到子图权重判别器内部的机器学习模型参数中。本章为子图权重判别器维护一个独立的优化器，该优化器只在一个轮次内所有子图结果计算并处理完成后才会更新判别器内的模型参数，即判别器的参数更新力度是一次完整的图快照序列处理轮次。这一梯度累加（Gradient Accumulation）机制的使用一方面可以加快判别器参数的训练速度，另一方面也可以使得判别器在一个完整的训练轮次中获得全部模型信息后再进行参数更新，保证了模型的稳定性和鲁棒性。

\subsubsection{子图划分策略}
如何确定子图大小是一个关键问题，如果划分得到的子图太大，模型计算的复杂度就会过高，且子图内部的社群特性会被削弱，子图权重判别器的重要性也会相对应地受到影响；而如果划分得到的子图太小，又会有过多的不同子图之间的节点间的边会被忽视掉，图数据中的拓扑信息又会过量流失，并且过小的机器学习模型也难以充分利用GPU算力，造成实质上的计算资源浪费，因此本文在实验部分详细探讨了子图切分大小对模型效果的综合影响。

\subsubsection{Offloading方法的若干实现细节}

上述并行训练流程的具体工程实现仍然涉及一系列关键细节，以下列举的是本章工作的实现中对这些细节的具体解释和解决方法描述：

\begin{itemize}
    \item GPU和CPU的工作量配比是工作调度的关键因素。对于典型的机器学习任务，现代GPU的工作效率往往能达到CPU的数十倍。这意味着在子图数量不多时，CPU提供的帮助相对有限，因此需要正确管理CPU中处理子图计算任务的并行度，否则CPU参与计算反而会拖慢全局训练速度。在本章的实现中，CPU一次仅处理一个子图对应的RSPSI模块的计算任务，在每个子图任务计算完成后检测GPU部分的处理状态并根据训练过程中总结的子图任务训练时间统计信息决定是否继续，这一做法将最小化总训练时间。
    
    \item 本章实现了简单的GPU-CPU协作处理的同步机制，通过条件变量的机制控制CPU和GPU处理线程交互。CPU计算线程和GPU计算线程在其计算结束后都会检查对方的等待状态，如果已经完成计算并进行等待，则说明此时全量计算已经完成，直接通知唤醒对应线程进行后续工作；如果发现对方仍处在计算状态中，则挂起自身以等待对方完成。
    \item 本章使用Offloading方法进行模型训练需要对模型使用的优化器进行相应的改动。由于常用的Adam\cite{kingma2017adammethodstochasticoptimization}优化器需要存储由模型参数多次更新计算得来的动量、均方差等累计值和统计值，而这些值也需要和模型参数处在同一设备上，因此在将子图上的RSPSI模型在GPU和CPU上通过Offloading方法移动时，也需要对优化器底层的状态变量进行对应的存储位置移动，从而使得训练过程能够正常进行，优化器能够正常发挥作用。
\end{itemize}

\section{本章小结}

本章介绍了基于前述已提出的RSPSI方法以及图机器学习领域常用的优化技巧，设计实现了基于划分子图后分块处理以及子图权重判别模型的源点检测方法CRSPSI，以及这一方法在监督学习训练模式和自监督学习训练模式上对应的CRSPSI-S和CRSPSI-E两种具体实现。
本章对图机器学习领域随社交网络图数据规模增大所面临的模型可扩展性问题进行深入分析，通过引入图分割以及基于子图的分块处理机制来确保模型在有限硬件条件下的可用性；通过构建子图权重判别器模型来捕获子图社群信息，平衡子图模块输出的数值差异；通过基于Offloading的方法来充分利用CPU计算资源，有效执行训练和预测流程。